home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 25 / Cream of the Crop 25.iso / utility / ffe101.zip / EXEC.SWG / 0006_BFF.pas < prev    next >
Pascal/Delphi Source File  |  1997-02-15  |  6KB  |  156 lines
  1. BFF: A grammar for Binary File Formats
  2.  
  3. With a growing number of binary formats that are being used, there is a
  4. need for specifying these formats in a well-defined way. Context free
  5. grammars have been used to specify the syntax of programming langauges. To
  6. use a grammar for binary file formats seems to be a logical choice.
  7.  
  8. In this page such a grammar, named BFF, is described. It has several
  9. construct that are not traditionally found in context free grammars for
  10. programming language. Due to the nature of binary file formats, it is
  11. important to be able to reference information that has been read before.
  12. For example, a string of characters might be preceded by a number that
  13. indicates the lengt of the string.
  14.  
  15. The terminal symbols of the grammar consist of a number of bytes,
  16. representing one of the basic data types, such as: char, short int, long
  17. int, float and double. Differences in byte ordering for integers, and the
  18. different formats for floating point numbers should be taken into account.
  19.  
  20. Due to the nature of binary formats, it is not too restrictive to use only
  21. recursive descent grammars, e.i., grammars that can be parsed top-down, and
  22. belong to the LL(1) class.
  23.  
  24. The BFF is tested for the DWG file format. As we start with this file
  25. format, BFF will naturally first focus on the requirements based on this
  26. format, and because of this it will be slightly biased.
  27.  
  28. To specify the grammar of BFF we will use a form of extended BNF.
  29.  
  30. Tool support for BFF
  31.  
  32. The first tool I am thinking about is a program that can read the grammar
  33. and apply this to a given binary file, resulting in an annotated output.
  34.  
  35. With this tool should also support the reverse engineering of binary file
  36. formats.
  37.  
  38. In a later state, a tool could be made that generates a parser and the
  39. needed data structures for reading a binary file into memory according to
  40. the grammar. As it is not always required (nor possible) to read the whole
  41. file into memory, it should be possible to generate procedures to read the
  42. file interactively.
  43.  
  44. The form of the BFF grammar
  45.  
  46. A grammar that describes a Binary File Format consists of the specification
  47. of the elementary units of data, and the rules by which these should be
  48. grouped together.
  49.  
  50. The elementary units
  51.  
  52. We assume that a Binary File can be viewed as a stream of bytes (as this is
  53. the most commonly used unit of data). Usually a number of bytes are grouped
  54. together to form data values that cannot be represented by a single byte.
  55. To specify a word value consisting of two bytes, for example, we propose
  56. the following defintion style:
  57.  
  58. type  word :=
  59.     byte : first,
  60.     byte : second
  61.     return ((word)first | ((word)second << 8)).
  62.  
  63. A word representation where the lower order byte comes before the higher
  64. order is usually used by small Endian processors. The expression used on
  65. will be based on C. We assume that the following types have been defined on
  66. top of the default types of C:
  67.  
  68. typedef unsigned char       byte;
  69. typedef unsigned short int  word;
  70. typedef unsigned long int   longword;
  71.  
  72. This leeds us to the definition of the basic types that will be supported:
  73.  
  74. C_data_types :=
  75.     "char"  | "byte" |
  76.     "short" | "word" |
  77.     "long"  | "longword" |
  78.     "float" | "double" .
  79.  
  80. (We assume for the moment that float and double represent floating numbers
  81. of 4, respectively 10 bytes.) The grammar of the rule used for defining
  82. types is:
  83.  
  84. type_def_rule :=
  85.      "typedef" C_data_type basic_type_name ":="
  86.      ("byte" ":" byte_name) LIST
  87.      "return" expr "." .
  88.  
  89. Here expr stands for C-like expression using the byte_names as they are
  90. used in the rule. The basic_type_names should not be confused with the
  91. C_type_names. It is possible that the same name is both used as a
  92. basic_type_name and a C_type_name.
  93.  
  94. The rules
  95.  
  96. The grammar that specifies in which order elementary units are taken from a
  97. binary file, makes use of non-terminal symbols and rules for each
  98. non-terminal symbol. There will be one non-terminal symbol that will parse
  99. the whole binary file, which will be called the root non-terminal symbol.
  100. For each non-terminal symbol there has to be a rule describing the elements
  101. it consists of, where each element is either an elementary elements or a
  102. non-terminal symbols. The rule of the root non-terminal symbol comes as the
  103. first rule, and is preceded with the word `root'. The whole BFF grammar
  104. follows the following grammar:
  105.  
  106. BFF_grammar :=
  107.      type_def_rule SEQ
  108.      "root" rule
  109.      rule SEQ.
  110.  
  111. Each rule has a non-terminal symbol on the left-hand side, and a list of
  112. elements on the right-hand side. Each element is either a elementary
  113. element, a non-terminal symbol, or a grouping of elements. Because BFF
  114. assumes a top-down parsing method, it is possible to give each non-terminal
  115. symbol a number of parameters. This leads to the following grammar for the
  116. rules:
  117.  
  118. rule :=
  119.       non_term_name  ( "(" param LIST ")" )OPT
  120.       ":=" elem LIST ".".
  121.  
  122. Each element consist of the following parts:
  123.  
  124.    * An (optional) range, which specifies the range of the file that
  125.      element may read.
  126.    * A data type, which can either be a elementary unit, a non-terminal
  127.      symbol, or a list of elements enclosed by brackets.
  128.    * An (optional) times expression, to indicate that the element can be
  129.      repeated, either for a given number of times or for an unknown number
  130.      of times.
  131.    * An (optional) identifying name, which can be used later to reference
  132.      the value found.
  133.    * An (optional) equivalence expression, which can be used for checking.
  134.  
  135. The following grammar describes an element:
  136.  
  137. elem := range OPT
  138.         data_type
  139.         ( "[" expr "]"
  140.         | "*" )
  141.         ( ":" elem_name )OPT
  142.         ( "=" C_expr )OPT.
  143.  
  144. range := "[" file_pos (":" file_pos)OPT "]".
  145.  
  146. file_pos := "begin" | "end" | "cur" | expr.
  147.  
  148. data_type := "(" elem LIST ")"
  149.            | basic_type_name
  150.            | non_term_name  ( "(" expr LIST ")" )OPT.
  151.  
  152. (To be continued ....)
  153.  
  154. ---------------------------------------------------------------------------
  155. Last update: Tuesday, 16-Jan-96 20:42:48 MET
  156.